package collection

type _avtNode[T any] struct {
	val    T
	parent *_avtNode[T]
	left   *_avtNode[T]
	right  *_avtNode[T]
	height int
}
type AVT[T any] struct {
	head    *_avtNode[T]
	len     int
	compare *func(a, b T) int
}

func CreateAVT[T any](compare func(a, b T) int) *AVT[T] {
	var a = new(AVT[T])
	a.compare = &compare
	a.head = new(_avtNode[T])
	return a
}

func (a *AVT[T]) Insert(v T) {
	now := a.head.left
	if now == nil {
		a.head.left = &_avtNode[T]{T, nil, nil, nil, 0}
	}
	flag := true
	for flag {
		switch (*a.compare)(now.val, v) {
		case -1:
			if now.right == nil {
				now.right = &_avtNode[T]{v, now, nil, nil, 1}
				flag = false
			} else {
				now = now.right
			}
			break
		case 1:
			if now.left == nil {
				now.left = &_avtNode[T]{v, now, nil, nil, 0}
				flag = false
			} else {
				now = now.left
			}
		case 0:
			return
		}
	}
	height := 2
	var nodeA *_avtNode[T]
	for pa := now; pa != nil; pa = pa.parent {
		k := 0
		if pa.left != nil {
			k += pa.left.height
		}
		if pa.right != nil {
			k -= pa.right.height
		}
		if (k < -1) || (k > 1) && nodeA == nil {
			nodeA = pa
		}
		if pa.height < height {
			pa.height = height
		} else {
			break
		}
	}

}
func (a *AVT[T]) Delete(v T) {
	var node *_avtNode[T]
	for now := a.head.left; now != nil; {
		switch (*a.compare)(now.val, v) {
		case 0:
			node = now
			now = nil
			break
		case -1:
			now = now.right
			break
		case 1:
			now = now.left
			break
		}

	}
	if node == nil {
		return
	}
	if node.left != nil {
		now := node.left
		for now.right != nil {
			now = now.right
		}
		node.val = now.val
		if now.parent.left == nil {
			now.parent.right = nil
			return
		}

	}
}
